package cn.edu.jxau.test;

import java.util.Arrays;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Queue;
import cn.edu.jxau.util.Stack;

/**
 * 使用搜索图中的路径。
 * 如果使用的是DFS寻路，所以所得的路径不是最短的。
 * 如果使用的是BFS寻路，所得路径是最短的。
 * 
 * @author 付大石
 */
public class Paths {

    public static void main(String[] args) {
        UndirectedGraph g = new UndirectedGraph(6);
        g.addEdge(0, 2);
        g.addEdge(0, 1);
        g.addEdge(0, 5);
        g.addEdge(2, 3);
        g.addEdge(5, 3);
        g.addEdge(3, 4);
        g.addEdge(2, 1);
        g.addEdge(2, 4);
        System.out.println(GraphUtils.toString(g));
        Paths p = new Paths(g, 0);
        for (int i = 0; i < g.v(); i++) {
            if(p.hasPathTo(i)) {
                for(int j : p.pathTo(i)) {
                    System.out.print(j+" ");
                }
                System.out.println();
            } else {
                System.out.println("没有到顶点"+i+"的路径");
            }
        }
    }

    /**
     * 标记
     */
    private boolean[] marked;

    /**
     * 路径信息
     */
    private int[] edgeTo;

    /**
     * 起点
     */
    private int start;

    public Paths(Graph g, int start) {
        this.start = start;
        marked = new boolean[g.v()];
        edgeTo = new int[g.v()];
//        dfs(g, start);
        bfs(g, start);
        System.out.println(Arrays.toString(edgeTo));
    }

    /**
     * 深度优先搜索算法
     */
    private void dfs(Graph g, int v) {

        marked[v] = true;
        for (int i : g.adj(v)) {
            if (!marked[i]) {
                marked[i] = true;
                edgeTo[i] = v; // 建立从start到i的路径信息
                dfs(g, i);
            }
        }
    }

    /**
     * 广度优先搜索算法
     */
    private void bfs(Graph g, int start) {

        Queue<Integer> queue = new LinkedQueue<>();
        queue.enqueue(start);
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            for (int i : g.adj(v)) {
                if (!marked[i]) {
                    marked[i] = true;
                    edgeTo[i] = v; // 建立从i到v的路径信息
                    bfs(g, i);
                }
            }
        }
    }

    /**
     * 判断从起点start出发是否有到v的路径
     * 
     * @param v
     * @return
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 获取从起点start出发到达v的路径
     * 
     * @param v
     * @return
     */
    public Iterable<Integer> pathTo(int v) {

        Stack<Integer> stack = new LinkedStack<>();
        while (v != start) {
            stack.push(v);
            v = edgeTo[v];
        }
        stack.push(start);
        return stack;
    }
}
